{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the City With the Smallest Number of Neighbors at a Threshold Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #dynamic-programming #shortest-path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #动态规划 #最短路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTheCity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #阈值距离内邻居最少的城市"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个城市，按从 <code>0</code> 到 <code>n-1</code> 编号。给你一个边数组 <code>edges</code>，其中 <code>edges[i] = [from<sub>i</sub>, to<sub>i</sub>, weight<sub>i</sub>]</code> 代表 <code>from<sub>i</sub></code> 和 <code>to<sub>i</sub></code><sub> </sub>两个城市之间的双向加权边，距离阈值是一个整数 <code>distanceThreshold</code>。</p>\n",
    "\n",
    "<p>返回能通过某些路径到达其他城市数目最少、且路径距离 <strong>最大</strong> 为 <code>distanceThreshold</code> 的城市。如果有多个这样的城市，则返回编号最大的城市。</p>\n",
    "\n",
    "<p>注意，连接城市 <em><strong>i</strong></em> 和 <em><strong>j</strong></em> 的路径的距离等于沿该路径的所有边的权重之和。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/26/find_the_city_01.png\" style=\"height: 225px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>城市分布图如上。\n",
    "每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：\n",
    "城市 0 -> [城市 1, 城市 2] \n",
    "城市 1 -> [城市 0, 城市 2, 城市 3] \n",
    "城市 2 -> [城市 0, 城市 1, 城市 3] \n",
    "城市 3 -> [城市 1, 城市 2] \n",
    "城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/26/find_the_city_02.png\" style=\"height: 225px; width: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>城市分布图如上。 \n",
    "每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：\n",
    "城市 0 -> [城市 1] \n",
    "城市 1 -> [城市 0, 城市 4] \n",
    "城市 2 -> [城市 3, 城市 4] \n",
    "城市 3 -> [城市 2, 城市 4]\n",
    "城市 4 -> [城市 1, 城市 2, 城市 3] \n",
    "城市 0 在阈值距离 2 以内只有 1 个邻居城市。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 100</code></li>\n",
    "\t<li><code>1 <= edges.length <= n * (n - 1) / 2</code></li>\n",
    "\t<li><code>edges[i].length == 3</code></li>\n",
    "\t<li><code>0 <= from<sub>i</sub> < to<sub>i</sub> < n</code></li>\n",
    "\t<li><code>1 <= weight<sub>i</sub>, distanceThreshold <= 10^4</code></li>\n",
    "\t<li>所有 <code>(from<sub>i</sub>, to<sub>i</sub>)</code> 都是不同的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]\\n4', '5\\n[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        edge_map = defaultdict(list)\n",
    "        for e1, e2, w in edges:\n",
    "            edge_map[e1].append([e2, w])\n",
    "            edge_map[e2].append([e1, w])\n",
    "\n",
    "        ans = [0, n + 1]\n",
    "        dis = [[float('inf') for _ in range(n)] for _ in range(n)]\n",
    "        for s in range(n):\n",
    "            dis[s][s] = 0\n",
    "\n",
    "        for e1, e2, w in edges:\n",
    "            dis[e1][e2] = w\n",
    "            dis[e2][e1] = w\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k])\n",
    "\n",
    "        for s in range(n - 1, -1, -1):\n",
    "            total = sum(p != s and dis[s][p] <= distanceThreshold for p in range(n))\n",
    "            if total < ans[1]:\n",
    "                ans[1] = total\n",
    "                ans[0] = s\n",
    "\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        adj = collections.defaultdict(set)\n",
    "        dist = collections.defaultdict(lambda: math.inf)\n",
    "        for a, b, *rest in edges:\n",
    "            if rest[0] <= distanceThreshold:\n",
    "                adj[a].add(b)\n",
    "                adj[b].add(a)\n",
    "                dist[a, b] = rest[0]\n",
    "                dist[b, a] = rest[0]\n",
    "        for k in range(n):\n",
    "            for a in adj[k]:\n",
    "                for b in adj[k]:\n",
    "                    if a == b:\n",
    "                        continue\n",
    "                    new_dist = dist[a, k] + dist[k, b]\n",
    "                    if new_dist <= min(dist[a, b], distanceThreshold):\n",
    "                        if dist[a, b] == math.inf:\n",
    "                            adj[a].add(b)\n",
    "                            adj[b].add(a)\n",
    "                        dist[a, b] = dist[a, k] + dist[k, b]\n",
    "        # print(dict(dist))\n",
    "        # print(dict(adj))\n",
    "        m = math.inf\n",
    "        r = 0\n",
    "        for a in range(n):\n",
    "            s = len(adj[a])\n",
    "            if s <= m:\n",
    "                m, r = s, a\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        graph = defaultdict(list)  # {node: [(neighbour, weight)]}\n",
    "        for u, v, w in edges:  # build graph\n",
    "            graph[u].append([v, w])\n",
    "            graph[v].append([u, w])\n",
    "        # Dijkstra\n",
    "        dp = [[float('inf')] * n for _ in range(n)]\n",
    "        pq = [[0, i, i] for i in range(n)]  # [dist, src, cur]\n",
    "        heapq.heapify(pq)\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0  # init\n",
    "        counter = {i: set() for i in range(n)}  # {src: {reachable nxt}}\n",
    "        while pq:\n",
    "            cur_dist, src, cur = heapq.heappop(pq)\n",
    "            if cur_dist > distanceThreshold or cur_dist > dp[src][cur]:\n",
    "                continue\n",
    "            for nxt, w in graph[cur]:\n",
    "                new_dist = cur_dist + w\n",
    "                if new_dist < dp[src][nxt] and new_dist <= distanceThreshold:\n",
    "                    dp[src][nxt] = new_dist\n",
    "                    heapq.heappush(pq, [new_dist, src, nxt])\n",
    "                    counter[src].add(nxt)\n",
    "        counter = sorted(counter.items(), key=lambda x: (len(x[1]), -x[0]))\n",
    "        return counter[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        city = {}\n",
    "        cur = []\n",
    "        for i in range(n):\n",
    "            city[i] = {}\n",
    "        for i in range(len(edges)):\n",
    "            x, y, w = edges[i]\n",
    "            if w <= distanceThreshold:\n",
    "                cur.append((x,y))\n",
    "                cur.append((y,x))\n",
    "                city[x][y] = w\n",
    "                city[y][x] = w\n",
    "        while cur:\n",
    "            nex = []\n",
    "            for x,y in cur:\n",
    "                for z in city[y]:\n",
    "                    if z == x:\n",
    "                        continue\n",
    "                    d = city[y][z] + city[x][y]\n",
    "                    if d <= distanceThreshold:\n",
    "                        if z in city[x] and city[x][z] <= d:\n",
    "                            continue\n",
    "                        city[x][z] = d\n",
    "                        city[z][x] = d\n",
    "                        nex.append((x,z))\n",
    "                        nex.append((z,x))\n",
    "            cur = nex\n",
    "        ans = -1\n",
    "        count = n + 1\n",
    "        for x in city:\n",
    "            if len(city[x]) < count:\n",
    "                count = len(city[x])\n",
    "                ans = x\n",
    "            elif len(city[x]) == count:\n",
    "                ans = max(ans, x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        graph = graph = [[distanceThreshold**100]*n for _ in range(n)]\n",
    "        print(graph)\n",
    "        cnt = [0]*n\n",
    "        for edge in edges:\n",
    "            graph[edge[0]][edge[1]] = edge[2]\n",
    "            graph[edge[1]][edge[0]] = edge[2]\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])\n",
    "\n",
    "        mins = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if graph[i][j] <= distanceThreshold and i!=j:\n",
    "                    cnt[i] += 1\n",
    "            if(cnt[i] <= mins):\n",
    "                mins = cnt[i]\n",
    "                res = i\n",
    "        return res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        f = [[[inf] * n for _ in range(n)] for _ in range(n + 1)]\n",
    "        for u, v, w in edges:\n",
    "            f[0][u][v] = f[0][v][u] = w\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    f[k + 1][i][j] = min(f[k][i][j], f[k][i][k] + f[k][k][j])\n",
    "        \n",
    "        ans, min_cnt = -1, n\n",
    "        for i in range(n):\n",
    "            cur_cnt = 0\n",
    "            for j in range(n):\n",
    "                if i != j and f[n][i][j] <= distanceThreshold:\n",
    "                    cur_cnt += 1\n",
    "            if cur_cnt <= min_cnt:\n",
    "                min_cnt = cur_cnt\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        f = [[[float(\"inf\")]*n for i in range(n)] for j in range(n+1)]\n",
    "        for i in range(n):\n",
    "                f[0][i][i] = 0\n",
    "\n",
    "        for i, j, v in edges:\n",
    "            f[0][i][j] = v\n",
    "            f[0][j][i] = v\n",
    "\n",
    "        for k in range(1, n+1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k-1]+f[k-1][k-1][j])\n",
    "\n",
    "        temp = [0]*n\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if f[n][i][j] <= distanceThreshold:\n",
    "                    temp[i] += 1\n",
    "                    temp[j] += 1\n",
    "        # print (temp)\n",
    "\n",
    "        minv = min(temp)\n",
    "        ans = None\n",
    "        for i, v in enumerate(temp):\n",
    "            if v == minv:\n",
    "                ans = i\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: [[int]], distanceThreshold: int) -> int:\n",
    "        # dp[i][j] distance of city i to j\n",
    "        dp = np.zeros((n, n), int)\n",
    "        dp.fill(-1)\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "        # initializer\n",
    "        for edge in edges:\n",
    "            dp[edge[0]][edge[1]] = edge[2]\n",
    "            dp[edge[1]][edge[0]] = edge[2]\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if dp[i][k] > -1 and dp[j][k] > -1 and (dp[i][j] > dp[i][k] + dp[k][j] or dp[i][j] == -1):\n",
    "                        dp[i][j] = dp[i][k] + dp[k][j]\n",
    "        minc = n\n",
    "        pset = set()\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if dp[i][j] > 0 and dp[i][j] <= distanceThreshold:\n",
    "                    cnt += 1\n",
    "            if minc >= cnt:\n",
    "                pset.clear()\n",
    "                minc = cnt\n",
    "                pset.add(i)\n",
    "\n",
    "        return pset.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        W = np.full((n, n), inf)\n",
    "        for i in range(n): W[i][i] = 0\n",
    "        for i, j, w in edges: W[i][j] = W[j][i] = w\n",
    "\n",
    "        for k in range(n): W = np.minimum(W, W[:, [k]] + W[[k]])\n",
    "\n",
    "        V = (W <= distanceThreshold).sum(-1)\n",
    "\n",
    "        i = 0\n",
    "        for j, m in enumerate(V):\n",
    "            if m <= n:\n",
    "                i, n = j, m\n",
    "        \n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        from typing import List\n",
    "        import numpy as np\n",
    "        setCity = set()\n",
    "        # 统计有哪些城市 \n",
    "        for i in range(n):\n",
    "            setCity.add(i)      \n",
    "            \n",
    "        # 初始化城市之间最短路径矩阵\n",
    "        lenth = len(setCity) # 路径矩阵行和列都是集合长度\n",
    "        distance = np.zeros((lenth, lenth))\n",
    "        for i in range(len(edges)): # 将直接相连的城市路径加入\n",
    "            distance[edges[i][0]][edges[i][1]] = edges[i][2]\n",
    "            distance[edges[i][1]][edges[i][0]]  = edges[i][2]\n",
    "        for i in range(lenth): # 将没有直接相连的城市之间的距离定义为无限\n",
    "            for j in range(lenth):\n",
    "                if i == j or distance[i][j] != 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    distance[i][j] = (10**4 + 1)    \n",
    "        \n",
    "        \n",
    "        # 计算城市之间最短路径矩阵 弗洛伊德算法\n",
    "        for k in range(lenth):\n",
    "            for i in range(lenth):\n",
    "                for j in range(lenth):\n",
    "                    dislen = distance[i, k] + distance[k, j]\n",
    "                    distance[i, j] = min(distance[i, j], dislen)\n",
    "                                    \n",
    "        # 筛选小于阈值距离的城市之间的距离并加入到纪录列表中\n",
    "        citynum = []\n",
    "        nums = [] # 记录能到达的城市的数量，并在方法后面取最小值\n",
    "        for i in range(lenth):\n",
    "            num = 0\n",
    "            for j in range(lenth):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if distance[i][j] <= distanceThreshold: # 记录小于阈值的城市数目\n",
    "                    num += 1\n",
    "            nums.append(num) \n",
    "            citynum.append([i, num]) # 记录能到达的城市的数量      \n",
    "            \n",
    "        # 到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市\n",
    "        city = []\n",
    "        for i in range(len(citynum)):\n",
    "            if citynum[i][1] == min(nums):\n",
    "                city.append(citynum[i][0])    \n",
    "        \n",
    "        return max(city) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        #dfs(k,i,j)=dfs(k−1,i,j)\n",
    "        #dfs(k,i,j)=dfs(k−1,i,k)+dfs(k−1,k,j)\n",
    "        w = [[10**4+1]* n for _ in range(n)]\n",
    "        for f, t, ww in edges:\n",
    "            w[f][t] = w[t][f] = ww\n",
    "        f = [[[0] * n for _ in range(n)] for _ in range(n+1)]\n",
    "        f[0] = w\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    f[k + 1][i][j] = min(f[k][i][j], f[k][i][k]+ f[k][k][j])\n",
    "        print(f)\n",
    "        ans = 0\n",
    "        min_cnt = inf\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if j != i and f[n][i][j] <= distanceThreshold:\n",
    "                    cnt += 1\n",
    "            if cnt <= min_cnt:\n",
    "                min_cnt = cnt\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.sparse import csr_matrix\n",
    "from scipy.sparse.csgraph import shortest_path\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        a, b, c = zip(*edges)\n",
    "        adjacency_matrix = csr_matrix((c, (a, b)), (n, n))\n",
    "        return sorted(enumerate((shortest_path(adjacency_matrix, directed=False) <= distanceThreshold).sum(axis=1)), key=lambda x: (x[1], -x[0]))[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        dis = [[inf] * n for _ in range(n)]\n",
    "        graph = defaultdict(list)\n",
    "        for i, j, w in edges:\n",
    "            dis[i][j] = w\n",
    "            dis[j][i] = w\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            # print(\"=================\")\n",
    "            for j in range(i):\n",
    "                dis[i][j] = dis[j][i]\n",
    "\n",
    "            lis = []\n",
    "            # 初始化\n",
    "            for jj in graph[i]:\n",
    "                heappush(lis, (dis[i][jj], i, jj))\n",
    "            \n",
    "            while lis:\n",
    "                # print(lis)\n",
    "                d, x, y = heappop(lis)\n",
    "                if dis[x][y] >= d:\n",
    "                    dis[x][y] = d\n",
    "                    for jj in graph[y]:\n",
    "                        if x != jj:\n",
    "                            heappush(lis, (dis[y][jj] + d, x, jj))\n",
    "\n",
    "        ans = -1\n",
    "        mincnt = inf\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if dis[i][j] <= distanceThreshold:\n",
    "                    cnt += 1\n",
    "            if mincnt >= cnt:\n",
    "                ans = i\n",
    "                mincnt = cnt\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        tree = defaultdict(list)\n",
    "        for from_, to_, weight in edges:\n",
    "            tree[from_].append([to_, weight])\n",
    "            tree[to_].append([from_, weight])\n",
    "        q = [(0, 0, 0)] # [(cnt, origin, current)]\n",
    "        ans = [set() for _ in range(n)]\n",
    "        visited = set() # origins\n",
    "        while q:\n",
    "            cnt, origin, cur = heapq.heappop(q)\n",
    "            if cnt > distanceThreshold:\n",
    "                break\n",
    "            if (cnt, origin, cur) in visited:\n",
    "                continue\n",
    "            if origin == cur:\n",
    "                visited.add((cnt, origin, cur))\n",
    "            else:\n",
    "                ans[origin].add(cur)\n",
    "            for to_, weight in tree[cur]:\n",
    "                if to_ not in ans[cur]:\n",
    "                    heapq.heappush(q, (0, to_, to_))\n",
    "                if to_ not in ans[origin]:\n",
    "                    heapq.heappush(q, (cnt+weight, origin, to_))\n",
    "        min_l, p = n, 0\n",
    "        for i, v in enumerate(ans):\n",
    "            if len(v) <= min_l:\n",
    "                min_l, p = len(v), i\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        nodes=[[] for _ in range(n)]\n",
    "        for f,to ,w in  edges:\n",
    "            nodes[f].append([to,w])\n",
    "            nodes[to].append([f,w])\n",
    "        res=[{} for _ in range(n)]\n",
    "        vis=[False]*n\n",
    "        @cache\n",
    "        def dfs(root,node,cur_d):\n",
    "            for t ,w in nodes[node]:\n",
    "                if cur_d+w <=distanceThreshold and not vis[t]:\n",
    "                    if t in res[root]:\n",
    "                        if cur_d+w<res[root][t]:\n",
    "                            res[root][t]=cur_d+w\n",
    "                            vis[t]=True\n",
    "                            dfs(root,t,cur_d+w)\n",
    "                            vis[t]=False\n",
    "                    else:\n",
    "                            res[root][t]=cur_d+w\n",
    "                            vis[t]=True\n",
    "                            dfs(root,t,cur_d+w)\n",
    "                            vis[t]=False\n",
    "                   \n",
    "                    \n",
    "        for i in range(n):\n",
    "            vis[i]=True\n",
    "            dfs(i,i,0)\n",
    "            vis[i]=False\n",
    "        minv=float('inf')\n",
    "        for i in res:\n",
    "            minv=min(minv,len(i))\n",
    "        # print(minv,res)\n",
    "        ans=0\n",
    "        for i in range(len(res)-1,-1,-1):\n",
    "            n=len(res[i])\n",
    "            if n==minv:\n",
    "                ans=max(ans,i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "\n",
    "        ll = [[10**9]*n for i in range(n)]\n",
    "        for a,b,c in edges:\n",
    "            ll[a][b] = ll[b][a] = c\n",
    "        @cache\n",
    "        def run(a,b,k):\n",
    "            if k < 0:\n",
    "                return ll[a][b]\n",
    "            if a>b:\n",
    "                return run(b,a,k)\n",
    "            return min(run(a,b,k-1), run(a,k,k-1) + run(k,b,k-1))\n",
    "        \n",
    "        ll2 = []\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            for j in range(n):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                t += 0 if run(i,j,n-1)>distanceThreshold else 1\n",
    "            ll2.append((t, -i))\n",
    "        \n",
    "        ll2.sort()\n",
    "        return -ll2[0][1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        te=[[0]*n for _ in range(n)]\n",
    "        tp={}\n",
    "        for e in edges:\n",
    "            if e[0] in tp:tp[e[0]]+=[e[1]]\n",
    "            else:tp[e[0]]=[e[1]]\n",
    "            if e[1] in tp:tp[e[1]]+=[e[0]]\n",
    "            else:tp[e[1]]=[e[0]]\n",
    "            te[e[0]][e[1]]=te[e[1]][e[0]]=e[2]\n",
    "        tm=[[99999]*n for _ in range(n)]\n",
    "        hp=[(0,[i]) for i in range(n)]\n",
    "        while hp:\n",
    "            (d,rt)=heapq.heappop(hp)\n",
    "            if tm[rt[0]][rt[-1]]!=99999:continue\n",
    "            tm[rt[0]][rt[-1]]=d\n",
    "            if rt[-1] not in tp:continue\n",
    "            for np in tp[rt[-1]]:\n",
    "                if np in rt:continue\n",
    "                if d+te[rt[-1]][np]>distanceThreshold:continue\n",
    "                heapq.heappush(hp,(d+te[rt[-1]][np],rt+[np]))\n",
    "        mi=99999\n",
    "        mii=0\n",
    "        for i in range(n):\n",
    "            m=sum((1 if x<=distanceThreshold else 0) for x in tm[i])\n",
    "            if m<=mi:\n",
    "                mi=m\n",
    "                mii=i\n",
    "        return mii"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        dct = defaultdict(dict)\n",
    "        for i, j, w in edges:\n",
    "            dct[i][j] = w\n",
    "            dct[j][i] = w\n",
    "\n",
    "        cnt = [set() for _ in range(n)]\n",
    "        stack = [[0, i, i] for i in range(n)]\n",
    "        while stack:\n",
    "            dis, start, cur = heapq.heappop(stack)\n",
    "            if dis > distanceThreshold:\n",
    "                break\n",
    "            if cur in cnt[start]:\n",
    "                continue\n",
    "            cnt[start].add(cur)\n",
    "            for nex in dct[cur]:\n",
    "                heapq.heappush(stack, [dis+dct[cur][nex], start, nex])\n",
    "\n",
    "        ans = 0\n",
    "        reach = n+1\n",
    "        for i in range(n):\n",
    "            if len(cnt[i]) <= reach:\n",
    "                ans = i\n",
    "                reach = len(cnt[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        graph={i:{} for i in range(n)}\n",
    "        for s,e,w in edges:\n",
    "            graph[s][e]=w\n",
    "            graph[e][s]=w\n",
    "        visit={i:{} for i in range(n)}\n",
    "        queue=[(i,i,0) for i in range(n)]\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            for (s,e,t) in queue:\n",
    "                if e not in visit[s]:\n",
    "                    visit[s][e]=t\n",
    "                    for nx in graph[e]:\n",
    "                        if t+graph[e][nx]<=distanceThreshold:\n",
    "                            temp.append((s,nx,t+graph[e][nx]))\n",
    "                elif t<visit[s][e]:\n",
    "                    visit[s][e]=t\n",
    "                    for nx in graph[e]:\n",
    "                        if t+graph[e][nx]<=distanceThreshold:\n",
    "                            temp.append((s,nx,t+graph[e][nx]))\n",
    "            queue=temp\n",
    "        return sorted(visit.items(),key=lambda x:(len(x[1]),-x[0]))[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        w = [[inf] * n for _ in range(n)]\n",
    "        for x, y, wt in edges:\n",
    "            w[x][y] = w[y][x] = wt\n",
    "\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(k: int, i: int, j: int) -> int:\n",
    "            # if i>j : return dfs(k,j,i)\n",
    "            if k < 0:  # 递归边界\n",
    "                return w[i][j]\n",
    "            return min(dfs(k - 1, i, j), dfs(k - 1, i, k) + dfs(k - 1, k, j))\n",
    "\n",
    "        ans = 0\n",
    "        min_cnt = inf\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if j > i and dfs(n - 1, i, j) <= distanceThreshold or j < i and dfs(n - 1, j, i) <= distanceThreshold:\n",
    "                    cnt += 1\n",
    "            if cnt <= min_cnt:  # 相等时取最大的 i\n",
    "                min_cnt = cnt\n",
    "                ans = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "\n",
    "        m = [[float(\"inf\")]*n for i in range(n)]\n",
    "        for i, j, v in edges:\n",
    "            m[i][j] = v\n",
    "            m[j][i] = v\n",
    "        for i in range(n):\n",
    "            m[i][i] = 0\n",
    "\n",
    "        memo = dict()\n",
    "        def f(k, i, j):\n",
    "            if (k,i,j) in memo:\n",
    "                return memo[(k,i,j)]\n",
    "            if k == -1:\n",
    "                memo[(k,i,j)] = m[i][j]\n",
    "                return m[i][j]\n",
    "            ans = min(f(k-1, i, j), f(k-1, i, k)+f(k-1, k, j))\n",
    "            memo[(k,i,j)] = ans\n",
    "            return ans\n",
    "\n",
    "        ans = [0]*n\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if f(n-1, i, j) <= distanceThreshold:\n",
    "                    ans[i] += 1\n",
    "                    ans[j] += 1\n",
    "\n",
    "        minv = min(ans)\n",
    "        res = None\n",
    "        for i, t in enumerate(ans):\n",
    "            if t == minv:\n",
    "                res = i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n",
    "        w = [[inf] * n for _ in range(n)]\n",
    "        for x, y, wt in edges:\n",
    "            w[x][y] = w[y][x]= wt\n",
    "        \n",
    "        @cache\n",
    "        def dfs(k: int, i: int, j: int) -> int:\n",
    "            if k < 0:\n",
    "                return w[i][j]\n",
    "            return min(dfs(k-1, i, j), dfs(k-1, i, k) + dfs(k-1, k, j))\n",
    "        \n",
    "        ans, min_cnt = -1, inf\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if i != j and dfs(n-1, i, j) <= distanceThreshold:\n",
    "                    cnt += 1\n",
    "            if cnt <= min_cnt:\n",
    "                ans = i\n",
    "                min_cnt = cnt\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
